\section{Algoritmo exacto}
\label{sec::exacto}

\subsection{Algoritmo y correctitud}

En primera instancia implementamos un algoritmo para resolver el problema de manera
exacta.

Puesto que el problema es NP-Completo, como ya mostramos en la secci\'on anterior,
no hab\'ia muchas esperanzas de obtener un algoritmo polin\'omico exacto para el
mismo (porque si lo hubieramos encontrado, estar\'iamos de viaje para cobrar el
mill\'on de dolares de premio). Nos conformamos entonces con implementar un algoritmo
de b\'usqueda exhaustiva lo mejor posible.

Para ello, aprovechando la reducci\'on en componentes conexas realizada en el apartado 
anterior de este trabajo, utilizamos una estrategia basada en acotar el tama\~no de la 
soluci\'on. El algoritmo se encuentra descripto en el Algoritmo~\ref{algo::exacto}.

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para resolver el problema de m\'inimo conjunto dominante de manera exacta, utilizando una estrategia
	en la cual se va acotando el tama\~no de un m\'inimo conjunto dominante y con eso . }
	\label{algo::exacto}
	\begin{algorithmic}
		\item var $cota, MCD, D$
		\Function{backtracking}{$G = (V,E), C \subseteq V$ compo. conexa}
			\If{$cota \leq | D |$}
				\State \Return
			\EndIf
			\If{$D$ es dominante de $G$}
				\If{$cota > |D|$}
					\State $cota \gets | D |$
					\State $MCD \gets D$
				\EndIf
				\Return
			\EndIf
			\ForAll{$v \in V \backslash D$}
				\State $D \gets D \bigcup \{ v \}$
				\State $backtracking(G)$
				\State $D \gets D - \{ v \}$
			\EndFor
		\EndFunction
		
		\Function{exacto}{$G = (V,E), C \subseteq V $ compo. conexa}
			\State \Comment{La cota empieza siendo un valor que ya sabemos sub\'optimo}
			\State $cota \gets \displaystyle 1+\left \lceil \frac{|C|}{2} \right \rceil$
			\Statex
			\State $D \gets \{ \}$
			\State $backtrack(G)$
			\State \Return $MCD$
		\EndFunction
	\end{algorithmic}
\end{algorithm}

Como puede verse el algoritmo consiste en una sencilla busqueda 
exhaustiva, con una poda basada en optimalidad de la cantidad de 
elementos de un m\'inimo conjunto dominante. Va probando los 
subconjuntos de nodos del grafo, tomando uno por uno y llamandose
de manera recursiva.

La eficiencia de esta estrategia se basa en que corta, especialmente si
la cota inicial es muy buena, muchas de las ramas de la b\'usqueda
exhaustiva.

Para tener una buena cota inicial, y aprovechando la reducci\'on al caso
de grafo conexo que realizamos en la secci\'on anterior, tenemos una por
el siguiente

\begin{lemma}
	Sea $G = (V,E)$ un grafo conexo y $D$ un m\'inimo conjunto dominante.
	Entonces $| D | \leq \displaystyle \left \lceil \frac{ | V | }{2} \right \rceil$.
\end{lemma}
\begin{proof}
	Puesto que $G$ es un grafo conexo, existe $T = (V_T, E_T)$ con
	$V_T = V$ y $E_T \subseteq E$ tal que $T$ es un \'arbol. Como un
	\'arbol es un grafo bipartito, podemos particionar $V = (U,W)$
	tal que no hay aristas en $T$ con ambos extremos en $U$ o en $W$.
	Tomando el m\'as chico de ambos conjuntos, tenemos un conjunto
	dominante.
	
	Para ver esto, supongamos sin p\'erdida de generalidad que $U$ es el
	conjunto con menor cantidad de elementos. Nos interesa ver que
	$\forall w \in W, \exists u \in U | (u,w) \in E_T$. 

	Esto es porque, al ser $T$ conexo, para todo $u \in U$ y todo $w \in W$
	debe haber un camino entre ellos. Como no hay aristas entre $u$ y
	otros nodos de $U$ y an\'alogo para $W$, el camino debe usar aristas
	que alternen entre $U$ y $W$. Sea $e$ la ultima arista que usa el 
	camino de $u$ a $w$. Puesto que un extremo es $w \in W$, el otro 
	extremo debe estar en $U$. Con lo cual tenemos que lo que 
	quer\'iamos ver.
	
	Por lo tanto entonces, como $v \in U$ o $v \in W$, vale que
	$\forall v \in V, v \in U \vee \exists w \in U | (u,w) \in E$ y
	entonces $U$ es conjunto dominante de $V$.
	
	Como es el m\'inimo de una bipartici\'on, tiene que ocurrir que la
	cantidad de elementos del conjunto es m\'as chica que la cantidad
	total de los mismos (sino no ser\'ia el m\'as chico).
	
	Finalmente entonces, vemos que un m\'inimo conjunto dominante debe
	tener menos que $\displaystyle \left \lceil \frac{| V |}{2} \right \rceil$ elementos, porque
	existe un conjunto dominante tal que tiene esa cantidad o menor que
	elementos.
$\hblacksquare$
\end{proof}

Por lo tanto la cota inicial presentada es correcta, considerando que
$C$ es una componente conexa del grafo $G$ y por lo tanto es un subgrafo
conexo del mismo.

La correctitud del algoritmo es obvia de que consiste en probar todos
los subconjuntos, acotados de manera de no revisar subconjuntos de los
nodos ya sabidos sub\'optimos. Esta cota es siempre correcta puesto que
al principio lo es, como ya demostramos, y cada vez que la actualizamos
es porque encontramos un conjunto dominante de menor cantidad de nodos.

Por lo tanto, usando la b\'squeda exhaustiva solo probamos los conjuntos 
interesantes al problema, pero como todo m\'inimo conjunto dominante es
un conjunto interesante al problema, y como examinamos una cantidad
finita de subconjuntos de un conjunto, eventualmente encontraremos alguno.

El algoritmo entonces termina. Cuando termina, es porque ning\'un 
subconjunto con menos elementos es dominante (porque sino lo hubieramos
encontrado al examinar exhaustivamente todos los subconjuntos, porque
los subconjuntos de menor cardinalidad que la soluci\'on devuelta no 
hubieran descartados por parte de la cota ya que sino la soluci\'on 
devuelta hubiera sido descartada). 
Por lo tanto, la soluci\'on cuando el algoritmo termina es efectivamente
un m\'inimo conjunto dominante del grafo original. El algoritmo es por
consiguiente correcto.

\subsection{Implementaci\'on en C++ y complejidad}

La implementaci\'on en C++ es directa del algoritmo presentado en
\ref{algo::exacto}. Utilizamos \texttt{vector<int>} para representar
los conjuntos de nodos, y la clase \texttt{Grafo} para representar el
grafo.

Se intent\'o programar este algoritmo de la manera m\'as efiicentemente
posible, evitando crear conjuntos temporales de nodos o realizando
chequeos ineficientes. Por ejemplo, para evitar tener que revisar en
cada paso cuales nodos fueron o no dominados para saber si ya se 
termin\'o con una rama, mantenemos esta cantidad en una variable que
vamos actualizando a medida que iteran los ciclos, y que en cada
llamada recursiva se va pasando por par\'ametro.

La complejidad del algoritmo la podemos obtener de la siguiente manera.
Sea $n = | V_c |, m = | E_c |$, donde $V_c$ es la cantidad de nodos
de la componente conexa que estamos examinando y $| V_c |$.

Sabemos que examinamos en peor caso examinamos todos los subconjuntos
de $\left \lceil \frac{n}{2} \right \rceil$ elementos de los $n$ 
v\'ertices de la componente. Este valor corresponde a 
$\displaystyle \binom{2n}{n}$. Si bien es posible obtener una mejor cota
de este valor que $2^n$, la misma es muy complicada (ya que requiere
utilizar la aproximaci\'on de Stirling). Por lo tanto nos quedamos con
que la cantidad de llamadas recursivas es $O(2^n)$.

El costo de una llamada recursiva depende de la implementaci\'on 
realizada. La versi\'on m\'as \'optima que logramos implementar tiene
complejidad interna $O(m)$ puesto que para probar cada nodo,
actualizamos un conjunto sobre arreglo redimensionable lo cual tiene
costo $O(1)$ amortizado. Para probar un nodo, necesitamos agregarlo al 
conjunto y contar cuantos nuevos nodos son dominados, antes de realizar 
la llamada recursiva. A la misma se le pasa por parametro la cantidad
de nodos ya cubiertos, lo cual evita costosos chequeos de dominancia
en el grafo y nos permite ir verificando esta condici\'on a medida que
lo vamos construyendo. Al mismo tiempo, para evitar revisar un mismo
conjunto de nodos del grafo en distinto \'orden, la funci\'on recibe
un par\'ametro que es el \'indice del \'ultimo nodo revisado, de manera
que cuando empieza a iterar los nodos, este es el primer valor que 
considera (y de esta manera si examinamos un conjunto de nodos este se
revisa solamente en su permutaci\'on en \'orden, que es \'unica).

Para poder marcar como dominados por un nodo m\'as a los vecinos de un
nodo, necesitamos iterar sobre todos ellos (para lo cual 
utilizamos el m\'etodo \texttt{vecinos} de la clase \texttt{Grafo})
y realizar una llamada recursiva. El costo total entonces es $O(m)$,
puesto que por cada nodo iteramos sobre sus vecinos, con lo cual en peor
caso miramos todas las aristas de la componente conexa.

La complejidad es entonces $O(m2^n)$. Esta cota no es asimpt\'oticamente
\'optima, puesto que no tiene en cuenta la poda realizada.
